\section{General reductions}

Left folds offer a great guarantee of strict left-to-right evaluation, allowing high flexibility for the fold operation.

However, when we work with operations that are associative $op(a, op(b,c)) == op(op(a,b),c)$ and commutative $op(a,b) == op(b,a)$, it really doesn’t matter what permutation of elements and order of operations we evaluate, we will always arrive at the same result.

This is why with the parallel support in C++17, we also received a batch of generalised reduction algorithms that reduce elements in unspecified order and permutation.

\subsection{\texorpdfstring{\cpp{std::reduce}}{\texttt{std::reduce}}}
\index{\cpp{std::reduce}}

The \cpp{std::reduce} algorithm is a generalised version of \cpp{std::accumulate}. That is, it reduces a range by applying the provided accumulation operation to the elements in unspecified order and permutation.

\cppversions{\texttt{reduce}}{\CC17}{\CC20}{\CC17}{N/A}
\constraints{\texttt{input\_range}}{\texttt{forward\_range}}{\texttt{std::plus<>()}}{\texttt{binary\_functor}}

Note that while we have access to a sequenced execution policy (i.e. \newline\cpp{std::execution::seq}), this does not make \cpp{std::reduce} sequenced in a left-fold sense.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/qxWsoM4Mf}{\ExternalLink}}
\footnotesize Example of using \cpp{std::reduce} with and without an execution policy.
\tcblower
\cppfile{code_examples/algorithms/reduce_code.h}
\end{codebox}

On top of the \cpp{std::accumulate} equivalents, we get one more overload that does away with the initial accumulator value, which removes the potential for using the wrong literal. Instead, the accumulator will be of the type of the ranges’ elements and will be value initialised.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/5PoEcEvd7}{\ExternalLink}}
\footnotesize Example of using \cpp{std::reduce} without specifying the initial value of the accumulator.
\tcblower
\cppfile{code_examples/algorithms/reduce_noinit_code.h}
\end{codebox}

The initial value of the accumulator will be “Quack” (line 2). Adding the other two ducks (line 8), we end up with “QuackQuackQuack”.

\subsection{\texorpdfstring{\cpp{std::transform_reduce}}{\texttt{std::transform\_reduce}}}
\index{\cpp{std::transform_reduce}}

The \cpp{std::transform_reduce} algorithm is the generalised counterpart to \linebreak\cpp{std::inner_product}. On top of the two-range variant, the algorithm also provides a unary overload.

\cppversions{\texttt{transform\_reduce}}{\CC17}{\CC20}{\CC17}{N/A}
\constraints{\texttt{input\_range}}{\texttt{forward\_range}}{N/A}{\texttt{(binary\_functor, unary\_functor)}}
\constraints{\texttt{(input\_range, input\_iterator)}}{\texttt{(forward\_range, forward\_iterator)}}{\texttt{(std::plus<>(), std::multiplies<>())}}{\texttt{(binary\_functor, binary\_functor)}}

\begin{codebox}[breakable]{\href{https://compiler-explorer.com/z/P8ohM19bW}{\ExternalLink}}
\footnotesize Example of using the unary version of \cpp{std::transform_reduce} to calculate a sum of squares and the binary version to calculate a sum of elements multiplied by coefficients.
\tcblower
\cppfile{code_examples/algorithms/transform_reduce_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::inclusive_scan}, \cpp{std::exclusive_scan}}{\texttt{std::inclusive\_scan}, \texttt{std::exclusive\_scan}}}
\index{\cpp{std::inclusive_scan}}
\index{\cpp{std::exclusive_scan}}

The \cpp{std::inclusive_scan} is a generalised version of \cpp{std::partial_sum}. On top of that, we also have access to \cpp{std::exclusive_scan}.

For \cpp{std::inclusive_scan}, the nth generated element is the sum of the first n source elements. For \cpp{std::exclusive_scan}, the nth element is the sum of the first n-1 source elements.

\cppversions{\texttt{inclusive\_scan}}{\CC17}{\CC20}{\CC17}{N/A}
\cppversions{\texttt{exclusive\_scan}}{\CC17}{\CC20}{\CC17}{N/A}

\constraints{\texttt{input\_range -> output\_iterator}}{\texttt{forward\_range -> forward\_iterator}}{\texttt{std::plus<>()}}{\texttt{binary\_functor}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/3hKaoczE3}{\ExternalLink}}
\footnotesize Example of using \cpp{std::inclusive_scan}.
\tcblower
\cppfile{code_examples/algorithms/inclusive_scan_code.h}
\end{codebox}

Consequently, because the first element generated by \cpp{std::exclusive_scan} is the sum of zero elements, we must specify an initial value of the accumulator, which will be the value of the first generated element.

\begin{codebox}[]{\href{https://compiler-explorer.com/z/eEc1PTv8G}{\ExternalLink}}
\footnotesize Example of using \cpp{std::exclusive_scan}.
\tcblower
\cppfile{code_examples/algorithms/exclusive_scan_code.h}
\end{codebox}

\subsection{\texorpdfstring{\cpp{std::transform_inclusive_scan},\newline\cpp{std::transform_exclusive_scan}}{\texttt{std::transform\_inclusive\_scan},\newline \texttt{std::transform\_exclusive\_scan}}}
\index{\cpp{std::transform_inclusive_scan}}
\index{\cpp{std::transform_exclusive_scan}}

The \cpp{std::transform_inclusive_scan} and \cpp{std::transform_exclusive_scan} algorithms are variants of \cpp{std::inclusive_scan} and \cpp{std::exclusive_scan} that apply a unary transformation function to each element before the reduction operation.

\cppversions{\texttt{transform\_inclu\dots}}{\CC17}{\CC20}{\CC17}{N/A}
\cppversions{\texttt{transform\_exclu\dots}}{\CC17}{\CC20}{\CC17}{N/A}
\constraints{\texttt{input\_range -> output\_iterator}}{\texttt{forward\_range -> forward\_iterator}}{N/A}{\texttt{(binary\_functor, unary\_functor)}}

\begin{codebox}[]{\href{https://compiler-explorer.com/z/oxdjMjY1c}{\ExternalLink}}
\footnotesize Example of using \cpp{std::transform_inclusive_scan} to accumulate absolute values of elements.
\tcblower
\cppfile{code_examples/algorithms/transform_inclusive_code.h}
\end{codebox}